#include <vector>
using namespace std;
int numTrees(int n) {
  // dp[i]: i个节点组成的互不相同的二叉搜索树的数量
  vector<int> dp(n + 1, 0);
  // 递推公式 dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]dp[0]
  // 初始化dp数组
  dp[0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < i; ++j) {
      dp[i] += dp[j] * dp[i - j - 1];
    }
  }
  return dp[n];
}